package com.study.algorithm.search;

public class KMP {
    public static void main(String[] args) {
        System.out.print(KMP("ABCABCX", "ABCX"));
    }

    public static int KMP(String s, String t) {
        int i = -1;
        int j = -1;
        int[] next = getNext(t);
        while (i < s.length() && j < t.length()) {
            if (j == -1 || s.charAt(i) == t.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == t.length()) {
            return i - t.length();
        } else {
            return -1;
        }
    }

    public static int[] getNext(String t) {
        int[] next = new int[t.length()];
        int i = 0;
        int j = -1;
        next[0] = -1;
        while (i < t.length() - 1) {
            if (j == -1 || t.charAt(i) == t.charAt(j)) {
                i++;
                j++;
                if (t.charAt(i) != t.charAt(j)) {
                    next[i] = j;
                } else {
                    next[i] = next[j];
                }
            } else {
                j = next[j];
            }
        }
        return next;
    }
}